package com.zyk.leetcode;

import java.util.HashSet;

/**
 * @author zhangsan
 * @date 2021/4/8 10:50
 */
public class M0208 {

    // https://leetcode-cn.com/problems/linked-list-cycle-lcci/
    // 暴力解: HashSet
    public static ListNode detectCycle(ListNode head) {
        ListNode cur = head;
        HashSet<ListNode> set = new HashSet<>();
        while (cur != null) {
            if(set.contains(cur)) {
                return cur;
            }
            set.add(cur);
            cur = cur.next;
        }
        return null;
    }

    // 快慢指针
    public static ListNode detectCycle2(ListNode head) {
        // 两个指针一起走, 快走二步,慢走一步, 如果相遇, 快从头走走一步,再次相遇.既是入环点
        // 快走到空, 代表没有环
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }

}
